home *** CD-ROM | disk | FTP | other *** search
/ NeXT Education Software Sampler 1992 Fall / NeXT Education Software Sampler 1992 Fall.iso / Programming / Source / WAIS / ir / irinv.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-02  |  27.6 KB  |  845 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    Brewster@think.com
  6. */
  7.  
  8.  
  9.  
  10. /* Inverted file accessor functions. 
  11.    
  12. Main functions:
  13.   finished_add_word
  14.  
  15. */
  16.  
  17.  
  18. #include <string.h> /* for memset() */
  19.  
  20. #include "cutil.h"
  21. #include "futil.h"
  22. #include "irhash.h"
  23. #include "panic.h"
  24. #include "irfiles.h"
  25. #include "irext.h"
  26.  
  27. /* ================== */
  28. /* === Index file === */
  29. /* ================== */
  30.  
  31. /*This is an implementation of the inverted file itself.
  32.  * An index_block_number is the position in the file that the
  33.  * entry starts.
  34.  * Index block 0 is the null pointer.
  35.  * The header contains the number of different words in the file.
  36.  *
  37.  */
  38.  
  39. /* the format of an index block is:
  40.  *  in the first byte:
  41.  *  INDEX_BLOCK_FULL_FLAG 
  42.  *    || INDEX_BLOCK_NOT_FULL_FLAG
  43.  *    || INDEX_BLOCK_DICTIONARY_FLAG
  44.  * if index_block_full_flag
  45.  *  next_index_block
  46.  *  index_block_size
  47.  *  stuff
  48.  *  (the number of valid entries is index_block_size - index_block_header_size)
  49.  * if index_block_not_full_flag
  50.  *  number_of_valid_entries
  51.  *  index_block_size
  52.  *  stuff
  53.  * if index_block_dictionary_flag
  54.  *  last_index_block      NEXT_INDEX_BLOCK_SIZE (0 when this is the last)
  55.  *  index_block_size      INDEX_BLOCK_SIZE_SIZE
  56.  *  number_of_occurances  NUMBER_OF_OCCURANCES_SIZE
  57.  *  word (followed by \n)
  58.  */
  59.  
  60. long 
  61. write_dictionary_index_block(number_of_occurances,word,stream)
  62. long number_of_occurances;
  63. char *word;
  64. FILE *stream;
  65. /* returns a pointer to the index block allocated */
  66. {
  67.   /* this assumes that the stream is positioned at the end */
  68.   long before_length = ftell(stream); /* file_length(stream); */
  69.   
  70.   long index_block_size = 
  71.     INDEX_BLOCK_FLAG_SIZE +
  72.       NEXT_INDEX_BLOCK_SIZE +
  73.     INDEX_BLOCK_SIZE_SIZE +
  74.       NUMBER_OF_OCCURANCES_SIZE +
  75.         strlen(word) +
  76.           strlen("\n");    /* this is done this way for PC's (necessary?) */
  77.   /* printf("writing dict entry to position %ld\n", before_length); */
  78.   /* grow the file */
  79.   /* in this implementation, the file is always filled by the fwrite,
  80.    * so it will grow itself.
  81.    grow_file(stream, before_length + how_large);
  82.    * file length leaves the stream at the end, so we are all set.
  83.    s_fseek(stream, before_length, SEEK_SET);
  84.    */
  85.   write_bytes(INDEX_BLOCK_DICTIONARY_FLAG, INDEX_BLOCK_FLAG_SIZE,
  86.           stream);    
  87.   write_bytes(0L, NEXT_INDEX_BLOCK_SIZE, stream);
  88.   write_bytes(index_block_size, INDEX_BLOCK_SIZE_SIZE, stream);
  89.  
  90.   write_bytes(number_of_occurances, NUMBER_OF_OCCURANCES_SIZE, 
  91.           stream);
  92.   fprintf(stream, "%s\n", word); 
  93.   /* just to check.  this will be unnecessary */
  94.   { long after_length = ftell(stream);
  95.     if(after_length - before_length != index_block_size){
  96.       waislog(WLOG_HIGH, WLOG_ERROR, 
  97.           "dictionary entry size is %ld, and we thought %ld",
  98.           after_length - before_length, index_block_size);
  99.     }
  100.   }
  101.   return(before_length);
  102. }
  103.  
  104. #ifdef everneeded
  105. static long modify_dictionary_index_block 
  106.   _AP((long index_block,long last_index_block,long number_of_occurances,
  107.        FILE* stream));
  108.  
  109. static long modify_dictionary_index_block(index_block,last_index_block,number_of_occurances,stream)
  110. long index_block;   
  111. long last_index_block;
  112. long number_of_occurances;
  113. FILE* stream;
  114.  
  115.      /* this does not allow one to change the word itself, only the entries 
  116.     around it.  It will panic if the index_block is not a valid block.
  117.     This returns the the stream to pointing at the end of the file.
  118.     */
  119. {
  120.   s_fseek(stream, index_block, SEEK_SET);
  121.   if(INDEX_BLOCK_DICTIONARY_FLAG != read_bytes(INDEX_BLOCK_FLAG_SIZE, stream))
  122.     panic("the index block %ld is not a legal dictionary block",
  123.       index_block);
  124.   write_bytes(number_of_occurances, NUMBER_OF_OCCURANCES_SIZE, 
  125.           stream);
  126.   write_bytes(last_index_block, NEXT_INDEX_BLOCK_SIZE, stream);
  127.   read_bytes(INDEX_BLOCK_SIZE_SIZE, stream); /* ignore it */
  128.   write_bytes(number_of_occurances, NUMBER_OF_OCCURANCES_SIZE, 
  129.           stream);
  130.   s_fseek(stream, 0L, SEEK_END);
  131. }
  132.  
  133. #endif /* def everneeded */
  134.  
  135. static long next_dictionary_index_block
  136.   _AP((long* index_block_size,long* number_of_occurances,char* word,
  137.        FILE* stream));
  138.  
  139. static long
  140. next_dictionary_index_block(index_block_size,number_of_occurances,word,stream)
  141. long *index_block_size;
  142. long *number_of_occurances;
  143. char *word;
  144. FILE *stream;
  145. {
  146.   /* this read the dictionary index block from the index stream.
  147.      It assumes the stream is positioned at the start of a dictionary
  148.      block, and will return non-0 if it is not.
  149.      returns 0 if it succeeds. */
  150.   long index_block_flag;
  151.   char temp[MAX_WORD_LENGTH + 2];
  152.   
  153.   word[0] = '\0';
  154.  
  155.   index_block_flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, stream);
  156.   if(index_block_flag == EOF)
  157.     return(-1);
  158.   if(index_block_flag != INDEX_BLOCK_DICTIONARY_FLAG)
  159.     panic("Did not find a dictionary entry, flag is %ld", index_block_flag);
  160.   (void)read_bytes(NEXT_INDEX_BLOCK_SIZE, stream);
  161.   *index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, stream);
  162.   *number_of_occurances = read_bytes(NUMBER_OF_OCCURANCES_SIZE,
  163.                      stream);
  164.   fgets(temp, MAX_WORD_LENGTH + 2, stream); /* 2 is for the \n and '\0' */
  165.  
  166.   /* trim the \n */
  167.   if(temp[strlen(temp) - 1] == '\n'){
  168.     temp[strlen(temp) - 1] = '\0';
  169.   }
  170.   strcpy(word, temp);
  171.      
  172.   return(0);
  173. }
  174.  
  175. #define testing
  176.  
  177. #ifdef testing
  178.  
  179. long
  180. read_dictionary_index_block(index_block,
  181.                 last_index_block,
  182.                 index_block_size,
  183.                 number_of_occurances,
  184.                 word,
  185.                 stream)
  186. long index_block;
  187. long *last_index_block;
  188. long *index_block_size;
  189. long *number_of_occurances;
  190. char *word;
  191. FILE *stream;
  192. {
  193.   /* this read the dictionary index block from the index stream.
  194.      returns 0 if it succeeds. */
  195.   long answer;
  196.   s_fseek(stream, index_block, SEEK_SET);
  197.   if(0 > (answer = next_dictionary_index_block(index_block_size,
  198.                             number_of_occurances,
  199.                             word,
  200.                             stream)))
  201.     panic("read dictionary block %ld failed", index_block);
  202.  
  203.   *last_index_block = 0;
  204.   return(answer);
  205. }
  206.  
  207. #endif /* def testing */
  208.  
  209. long allocate_index_block(how_large,stream)
  210. long how_large;
  211. FILE* stream;
  212. {
  213.   /* This returns a pointer for an index block.
  214.      It creates the space and writes the header.
  215.      how_large includes the header.
  216.      Returns the block_number (the byte address of first byte in the block */
  217.   /* this assumes that the stream is positioned at the end */
  218.   long before_length = ftell(stream); /* file_length(stream); */
  219.   /* grow the file */
  220.   /* in this implementation, the file is always filled by the fwrite,
  221.    * so it will grow itself.
  222.    grow_file(stream, before_length + how_large);
  223.    * file length leaves the stream at the end, so we are all set.
  224.    s_fseek(stream, before_length, SEEK_SET);
  225.    */
  226.   write_bytes(INDEX_BLOCK_FULL_FLAG, /* in this version all are full */
  227.           INDEX_BLOCK_FLAG_SIZE,
  228.           stream);
  229.   write_bytes(0L, NEXT_INDEX_BLOCK_SIZE, stream);
  230.   write_bytes(how_large, INDEX_BLOCK_SIZE_SIZE, stream);
  231.   return(before_length);
  232. }
  233.  
  234. #ifdef testing
  235.  
  236. static void scan_index_blocks _AP((char* filename,boolean verbose));
  237.  
  238. static void scan_index_blocks(filename,verbose)
  239. char *filename;
  240. boolean verbose;
  241. {
  242.   /* this is a debugging routine for checking the inverted index file */
  243.   long current_index_block = INDEX_HEADER_SIZE;
  244.   FILE *stream = s_fopen(filename, "rb");
  245.   long length = file_length(stream);
  246.   
  247.   s_fseek(stream, current_index_block, SEEK_SET);
  248.   printf("File length %ld\n", length);
  249.  
  250.   while(current_index_block < length){
  251.     long flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, stream);
  252.     long next_index_block = read_bytes(NEXT_INDEX_BLOCK_SIZE, stream);
  253.     long index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, stream);
  254.     if(flag == INDEX_BLOCK_DICTIONARY_FLAG){
  255.       long last_index_block;
  256.       long index_block_size;
  257.       long number_of_occurances;
  258.       char word[MAX_WORD_LENGTH + 1];
  259.       if(0 > read_dictionary_index_block(current_index_block,
  260.                   &last_index_block,
  261.                   &index_block_size,
  262.                   &number_of_occurances,
  263.                   word,
  264.                   stream))
  265.     panic("read dictionary index block failed");
  266.       if(verbose)
  267.     printf("%5ld: size %3ld Dictionary entry '%s', number of occurances %ld last block %ld\n",
  268.            current_index_block, index_block_size, word, 
  269.            number_of_occurances, next_index_block);
  270.     }
  271.     else if(flag == INDEX_BLOCK_NOT_FULL_FLAG){
  272.       if(verbose)
  273.     printf("%5ld: size %3ld Not full, valid entries %ld\n",
  274.            current_index_block, index_block_size, next_index_block);
  275.     }
  276.     else if(flag == INDEX_BLOCK_FULL_FLAG){
  277.       if(verbose)
  278.     printf("%5ld: size %3ld full block, next block %ld\n",
  279.          current_index_block, index_block_size, next_index_block);
  280.     }
  281.     else 
  282.       panic("bad entry %ld (ftell %ld), flag was %ld", 
  283.         current_index_block, 
  284.         ftell(stream), flag);
  285.     current_index_block += index_block_size;
  286.     s_fseek(stream, current_index_block, SEEK_SET);
  287.   }
  288.   s_fclose(stream);
  289. }   
  290.  
  291. #endif /* def testing */
  292.  
  293. #define COPY_BLOCK_BUFFER_LENGTH 1000
  294.  
  295. static long copy_stream _AP((FILE* from_stream,FILE* to_stream,long n));
  296.  
  297. static long copy_stream(from_stream,to_stream,n)
  298. FILE *from_stream;
  299. FILE *to_stream;
  300. long n;
  301. {
  302.   char buffer[COPY_BLOCK_BUFFER_LENGTH];
  303.   while(n > 0){
  304.     /* keep reading until we are done */
  305.     long amount_read = fread(buffer, sizeof(char), 
  306.                  MIN(n, COPY_BLOCK_BUFFER_LENGTH),
  307.                  from_stream);
  308.     if(amount_read == 0 || amount_read == EOF)
  309.       return(-1);
  310.     if(amount_read != fwrite(buffer, sizeof(char), amount_read, to_stream))
  311.       return(-1);
  312.     n -= amount_read;
  313.   }
  314.   return(0);
  315. }
  316.  
  317.  
  318. static void merge_blocks _AP((char* word,FILE* from_stream_1,
  319.                   FILE* from_stream_2,FILE* to_stream));
  320.  
  321. static void merge_blocks(word,from_stream_1,from_stream_2,to_stream)
  322. char* word;
  323. FILE *from_stream_1;
  324. FILE *from_stream_2;
  325. FILE *to_stream;
  326. /* puts from_stream_1 first into to_stream then from_stream_2*/
  327. {
  328.   long flag;
  329.   long index_block_size;
  330.   long other_block_size;
  331.     
  332.   flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, from_stream_1);
  333.   (void)read_bytes(NEXT_INDEX_BLOCK_SIZE, from_stream_1);
  334.   index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, from_stream_1);
  335.  
  336.   if(flag == EOF) return;
  337.   if(flag != INDEX_BLOCK_FULL_FLAG)
  338.     panic("the next index block is not a full block");
  339.  
  340.   flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, from_stream_2);
  341.   (void)read_bytes(NEXT_INDEX_BLOCK_SIZE, from_stream_2);
  342.   other_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, from_stream_2);
  343.   if(flag != INDEX_BLOCK_FULL_FLAG)
  344.     panic("the next index block is not a full block");
  345.  
  346.   write_bytes(flag, INDEX_BLOCK_FLAG_SIZE, to_stream);
  347.   write_bytes(0L, NEXT_INDEX_BLOCK_SIZE, to_stream);
  348.   if((index_block_size + other_block_size) >
  349.      (1L << (INDEX_BLOCK_SIZE_SIZE * 8))){
  350.     /* then the block is too large to be represented in the 
  351.        index_block_size_size.  This routine takes the radical step to
  352.        eliminate it completely.  The "right" thing to do is to
  353.        chain blocks, but I dont think it is worth it since this should not
  354.        happen very often.  If it does happen often then bump up
  355.        INDEX_BLOCK_SIZE_SIZE. */
  356.     waislog(WLOG_HIGH, WLOG_ERROR, 
  357.         "Can not merge the index block for %s, since it would create one that is too big.  Deleting it.",word);
  358.     write_bytes(INDEX_BLOCK_HEADER_SIZE, INDEX_BLOCK_SIZE_SIZE, to_stream);
  359.     s_fseek(from_stream_1, index_block_size - INDEX_BLOCK_HEADER_SIZE, SEEK_CUR);
  360.     s_fseek(from_stream_2, other_block_size - INDEX_BLOCK_HEADER_SIZE, SEEK_CUR);
  361.   }
  362.   else{ /* copy away */
  363.     write_bytes(index_block_size + other_block_size - INDEX_BLOCK_HEADER_SIZE, 
  364.         INDEX_BLOCK_SIZE_SIZE, to_stream);
  365.     copy_stream(from_stream_1, to_stream, index_block_size - INDEX_BLOCK_HEADER_SIZE);
  366.     copy_stream(from_stream_2, to_stream, other_block_size - INDEX_BLOCK_HEADER_SIZE);
  367.   }
  368. }
  369.  
  370. static void make_dummy_block _AP((FILE* from_stream_1,FILE* from_stream_2,
  371.                   FILE* to_stream));
  372.  
  373. static void make_dummy_block(from_stream_1,from_stream_2,to_stream)
  374. FILE *from_stream_1;
  375. FILE *from_stream_2;
  376. FILE *to_stream;
  377. /* deletes block from_stream_1 and from_stream_2 and makes a 0 length
  378.    block on to_stream */
  379. {
  380.   long flag;
  381.   long index_block_size;
  382.   long other_block_size;
  383.     
  384.   flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, from_stream_1);
  385.   (void)read_bytes(NEXT_INDEX_BLOCK_SIZE, from_stream_1);
  386.   index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, from_stream_1);
  387.  
  388.   if(flag == EOF) return;
  389.   if(flag != INDEX_BLOCK_FULL_FLAG)
  390.     panic("the next index block is not a full block");
  391.  
  392.   flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, from_stream_2);
  393.   (void)read_bytes(NEXT_INDEX_BLOCK_SIZE, from_stream_2);
  394.   other_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, from_stream_2);
  395.   if(flag != INDEX_BLOCK_FULL_FLAG)
  396.     panic("the next index block is not a full block");
  397.  
  398.   write_bytes(flag, INDEX_BLOCK_FLAG_SIZE, to_stream);
  399.   write_bytes(0L, NEXT_INDEX_BLOCK_SIZE, to_stream);
  400.   write_bytes(INDEX_BLOCK_HEADER_SIZE, INDEX_BLOCK_SIZE_SIZE, to_stream);
  401.   s_fseek(from_stream_1, index_block_size - INDEX_BLOCK_HEADER_SIZE, SEEK_CUR);
  402.   s_fseek(from_stream_2, other_block_size - INDEX_BLOCK_HEADER_SIZE, SEEK_CUR);
  403. }
  404.  
  405. static void copy_block _AP((FILE* from_stream,FILE* to_stream));
  406.  
  407. static void copy_block(from_stream,to_stream)
  408. FILE *from_stream;
  409. FILE *to_stream;
  410. /* copies an index block from one stream to another */
  411. { /* copies an index block from from_stream to to_stream */
  412.   long flag;
  413.   long next_index_block;
  414.   long index_block_size;
  415.  
  416.   flag = read_bytes(INDEX_BLOCK_FLAG_SIZE, from_stream);
  417.   next_index_block = read_bytes(NEXT_INDEX_BLOCK_SIZE, from_stream);
  418.   index_block_size = read_bytes(INDEX_BLOCK_SIZE_SIZE, from_stream);
  419.  
  420.   if(flag == EOF) return;
  421.   write_bytes(flag, INDEX_BLOCK_FLAG_SIZE, to_stream);
  422.   write_bytes(next_index_block, NEXT_INDEX_BLOCK_SIZE, to_stream);
  423.   write_bytes(index_block_size, INDEX_BLOCK_SIZE_SIZE, to_stream);
  424.   /* copy the real stuff */
  425.   copy_stream(from_stream, to_stream, 
  426.           index_block_size - INDEX_BLOCK_HEADER_SIZE);
  427. }
  428.  
  429. /* ================== */
  430. /* === Merge File === */
  431. /* ================== */
  432.  
  433. static boolean merge_index_file _AP((long from_version, long into_version,
  434.                   database* db,
  435.                   boolean generate_dictionary));
  436.  
  437. /* Merges a index file (from_version) into another (into_version).
  438.    Returns true if successful */
  439. static boolean merge_index_file(into_version, from_version, 
  440.                 db,generate_dictionary)
  441. long into_version;
  442. long from_version;
  443. database* db;
  444. boolean generate_dictionary;
  445. /* 
  446.    This is done by merging both into version -1 and then, 
  447.    renames it to into_version, then deletes from_version. */
  448. {
  449.   char input_filename_1[MAX_FILENAME_LEN]; /* into_version file */
  450.   char input_filename_2[MAX_FILENAME_LEN]; /* from_version file */
  451.   char output_filename[MAX_FILENAME_LEN];  /* version -1 */
  452.  
  453.   FILE *input_stream_1;
  454.   FILE *input_stream_2;
  455.   FILE *output_stream;
  456.   char input_word_1[MAX_WORD_LENGTH + 1];
  457.   char input_word_2[MAX_WORD_LENGTH + 1];
  458.   long number_of_words_1;
  459.   long number_of_words_2;
  460.  
  461.   if(generate_dictionary) {
  462.     waislog(WLOG_MEDIUM, WLOG_INDEX,
  463.         "Merging version %ld into %ld generating dictionary.",
  464.         from_version, into_version);
  465.   }
  466.   else {
  467.     waislog(WLOG_MEDIUM, WLOG_INDEX, "Merging version %ld and %ld", 
  468.         into_version, from_version);
  469.   }
  470.  
  471.   index_filename_with_version(into_version, input_filename_1, db);
  472.   index_filename_with_version(from_version, input_filename_2, db); 
  473.   index_filename_with_version(-1L, output_filename, db); 
  474.   
  475.  
  476.   if(NULL == (input_stream_1 = s_fopen(input_filename_1, "rb")))
  477.     return(false);
  478.  
  479.   if(NULL == (input_stream_2 = s_fopen(input_filename_2, "rb")))
  480.     return(false);
  481.  
  482.   if(NULL == (output_stream = s_fopen(output_filename, "wb")))
  483.     return(false);
  484.  
  485.   {
  486.     long index_block_size_1;
  487.     long number_of_occurances_1;
  488.     long index_block_size_2;
  489.     long number_of_occurances_2;
  490.     number_of_words_1 = read_bytes(INDEX_HEADER_SIZE, input_stream_1);
  491.     number_of_words_2 = read_bytes(INDEX_HEADER_SIZE, input_stream_2);
  492.     /* printf("Number of words 1: %ld, 2: %ld\n", number_of_words_1, number_of_words_2); */
  493.     db->number_of_words = 
  494.       ((EOF != number_of_words_1) ? number_of_words_1 : 0) +
  495.     ((EOF != number_of_words_2) ? number_of_words_2 : 0);
  496.  
  497.     write_bytes(db->number_of_words, INDEX_HEADER_SIZE, output_stream);
  498.     if(generate_dictionary)
  499.       init_dict_file_for_writing(db);
  500.  
  501.     next_dictionary_index_block(&index_block_size_1,
  502.                 &number_of_occurances_1,
  503.                 input_word_1,
  504.                 input_stream_1);
  505.     next_dictionary_index_block(&index_block_size_2,
  506.                 &number_of_occurances_2,
  507.                 input_word_2,
  508.                 input_stream_2);
  509.     while(true){
  510.       long strlen_1 = strlen(input_word_1);
  511.       long strlen_2 = strlen(input_word_2);
  512.       long compare = strcmp(input_word_1, input_word_2); /* +1 if 1 is bigger */
  513.  
  514.       if((0 == strlen_1) && 
  515.      (0 == strlen_2)){
  516.     /* printf("Done with merge\n"); */
  517.     /* then we are done. */
  518.     break;
  519.       }
  520.       else if((0 != strlen_1) && (0 != strlen_2) && (0 == compare)){
  521.     /* they are equal */
  522.     /* printf("Merging word %s and %s\n", input_word_1, input_word_2); */
  523.     write_dictionary_index_block(number_of_occurances_1 +
  524.                      number_of_occurances_2, 
  525.                      input_word_1, 
  526.                      output_stream);
  527.     if(generate_dictionary)
  528.       add_word_to_dictionary(input_word_1, ftell(output_stream), 
  529.                  number_of_occurances_1 + number_of_occurances_2, 
  530.                  db);
  531.     /* copy file 1 first.  this assumes that file 1 was indexed before
  532.        file 2 */
  533.     if((number_of_occurances_1+number_of_occurances_2) > MAX_OCCURANCES){
  534.       /* too many already, just make a dummy (0 length) */
  535.       if((number_of_occurances_1 < MAX_OCCURANCES) &&
  536.          (number_of_occurances_2 < MAX_OCCURANCES)) {
  537.         /* only print the first time */
  538.         waislog(WLOG_MEDIUM, WLOG_INDEX,
  539.             "Deleting word '%s' since it has %ld occurances (limit %ld).",
  540.             input_word_1, number_of_occurances_1+number_of_occurances_2,
  541.             MAX_OCCURANCES);
  542.       }
  543.       make_dummy_block(input_stream_1, input_stream_2, output_stream);
  544.     }
  545.     else{
  546.       merge_blocks(input_word_1,input_stream_1,input_stream_2,
  547.                output_stream); 
  548.     }
  549.     next_dictionary_index_block(&index_block_size_1,
  550.                     &number_of_occurances_1,
  551.                     input_word_1,
  552.                     input_stream_1);
  553.     next_dictionary_index_block(&index_block_size_2,
  554.                     &number_of_occurances_2,
  555.                     input_word_2,
  556.                     input_stream_2);
  557.       }
  558.       else if(((0 == strlen_1) && (0 != strlen_2) && (0 > compare)) ||
  559.           ((0 != strlen_1) && (0 != strlen_2) && (0 < compare))){
  560.     /* write from block 2 */
  561.     /* printf("From block 2: writing word '%s' not '%s'\n", 
  562.        input_word_2, input_word_1);  */
  563.     write_dictionary_index_block(number_of_occurances_2, input_word_2,
  564.                      output_stream);
  565.     if(generate_dictionary)
  566.       add_word_to_dictionary(input_word_2, ftell(output_stream), 
  567.                  number_of_occurances_2, db);
  568.     copy_block(input_stream_2, output_stream);
  569.     next_dictionary_index_block(&index_block_size_2,
  570.                     &number_of_occurances_2,
  571.                     input_word_2,
  572.                     input_stream_2);
  573.       }
  574.       else{
  575.     /* write from block 1 */
  576.     /* printf("From block 1: writing word '%s' not '%s'\n", 
  577.        input_word_1, input_word_2); */
  578.     write_dictionary_index_block(number_of_occurances_1, input_word_1,
  579.                      output_stream);
  580.     if(generate_dictionary)
  581.       add_word_to_dictionary(input_word_1, ftell(output_stream), 
  582.                  number_of_occurances_1, db);
  583.     copy_block(input_stream_1, output_stream);
  584.     next_dictionary_index_block(&index_block_size_1,
  585.                     &number_of_occurances_1,
  586.                     input_word_1,
  587.                     input_stream_1);
  588.       }
  589.     }
  590.   }
  591.   s_fclose(input_stream_1);
  592.   s_fclose(input_stream_2);
  593.   s_fclose(output_stream);
  594.   /* check resulting file */    
  595.   /* check_index_file(output_filename); */
  596.   /* scan_index_blocks(output_filename); */
  597.  
  598.   /* delete the input files */
  599.   remove(input_filename_1);
  600.   remove(input_filename_2);
  601.   rename(output_filename, input_filename_1);
  602.  
  603. #ifdef THINK_C
  604.   /* set the mac file type to INDX */
  605.   setFileType(input_filename_1, WAIS_INDEX_FILE_TYPE, CREATOR);
  606. #endif /* THINK_C */
  607.   return(true);
  608. }
  609.  
  610. /* only works on positive, non-zero numbers, and is slow to boot, yippie */
  611. static long logcount _AP((long number));
  612. static long logcount(number)
  613. long number;
  614. {
  615.   long answer = 0;
  616.   for( ; number > 0; number = number >> 1)
  617.     answer++;
  618.   return(answer);
  619. }
  620.     
  621.  
  622. static void merge_index_files _AP((database* db));
  623.  
  624. static void merge_index_files(db)
  625. database *db;
  626. /* this merges all the temporary inverted files into a large on 
  627.  * and creates a dictionary.
  628.  * This is done in a logrithmic merge of the files.
  629.  * An n-ary merge would be faster of course, but what the heck... 
  630.  */
  631. {
  632.   /* this version does it two at a time */
  633.   char filename[MAX_FILENAME_LEN];
  634.   char filename2[MAX_FILENAME_LEN];
  635.   long level;
  636.   long final_level;
  637.   long number_of_files_to_merge = db->index_file_number;
  638.   /* at level 0, merge 0,1->0; 2,3->2; 4,5->4; 6,7->6; 
  639.      at level 1, merge 0,2->0; 4,6->4;
  640.      at level 2, merge 0,4->0;
  641.      stop.
  642.      If there is only 1 file, then dont merge (final_level will be -1),
  643.      the dictionary will be generated by merge after the for loop.
  644.      */
  645.   final_level = logcount(number_of_files_to_merge - 1) - 1;
  646.   for(level = 0; level <= final_level; level++){
  647.     long into_version;
  648.     for(into_version = 0; 
  649.     into_version < number_of_files_to_merge; 
  650.     into_version += (2 << level)){
  651.       long from_version = into_version + (1 << level);
  652.       if(from_version < number_of_files_to_merge){
  653.     boolean generate_dictionary; /* if this is the final level and 
  654.                     there is no .inv file then yes */
  655.     if(level == final_level){
  656.       if(probe_file(index_filename(filename, db)))
  657.         generate_dictionary = false;
  658.       else generate_dictionary = true;
  659.     }
  660.     else{ 
  661.       generate_dictionary = false;
  662.     }
  663.     
  664.     /* printf("Level %d (out of %d) merging into %d from %d\n", 
  665.            level, final_level, into_version, from_version); */
  666.     if(false == merge_index_file(into_version, from_version, db,
  667.                      generate_dictionary))
  668.       panic("Error in merging file %ld into %ld", 
  669.         from_version, into_version);
  670.       }
  671.     }
  672.   } /* done merging */
  673.   /* if there is a .inv file, then we are adding to an existing db. merge */ 
  674.   if(probe_file(index_filename(filename, db))){
  675.     /* printf("Merging into existing db\n"); */
  676.     /* rename the .inv file to 1, then merge it into 0 */
  677.     rename(index_filename(filename, db),
  678.        index_filename_with_version(1L, filename2, db));
  679.     merge_index_file(0L, 1L, db, true);    
  680.   }
  681.   else if(number_of_files_to_merge == 1){
  682.     /* then we have to generate a dictionary for this one file. 
  683.        create a dummy file in 1, then merge that while making a dictionary
  684.        */
  685.     touch_file(index_filename_with_version(1, filename, db));
  686.     merge_index_file(0L, 1, db, true);
  687.   }
  688.   /* rename 0 into the final name */
  689.   rename(index_filename_with_version(0L,filename2, db),
  690.      index_filename(filename, db));
  691. }    
  692.  
  693. /* ============================================ */
  694. /* ===  Flushing the memory version of the  === */
  695. /* ===  word hashtable to disk files        === */
  696. /* ============================================ */
  697.  
  698. static void flush_word_entry_to_file _AP((word_entry* wrd_entry,
  699.                       database* db));
  700.  
  701. static void flush_word_entry_to_file(wrd_entry,db)
  702. word_entry* wrd_entry;
  703. database* db;
  704. {
  705.   /* In this version, each word_entry is made into an index block.
  706.      This means that there may be many small index blocks if the memory
  707.      can not hold many files worth of data.  This approach was taken 
  708.      for simplicities sake and it might be the best approach if there
  709.      is a small vocabulary.
  710.      
  711.      This assumes that the index stream is positioned at the end.
  712.      */
  713.  
  714.   if(wrd_entry->number_of_occurances > MAX_OCCURANCES){
  715.     /* there are too many of this word, do nothing.
  716.      * this may result in some having been written before, or 
  717.      * no occurances of this word might be recorded.  Is this right?
  718.      * if the first MAX_OCCURANCES want to be recored, then
  719.      * add this clause to this condition:
  720.      *     && wrd_entry->starting_block_number != 0
  721.      */
  722.     return;
  723.   }
  724.   if((wrd_entry->current_memory_ptr - wrd_entry->memory_ptr) >
  725.      (1L << (8 * INDEX_BLOCK_SIZE_SIZE)))
  726.     return; /* there are too many entries to store away, therefore throw it all away */
  727.   
  728.   if(NULL == wrd_entry->memory_ptr){
  729.     /* not entries to write out */
  730.     return;
  731.   }
  732.   if(0 == (wrd_entry->current_memory_ptr - wrd_entry->memory_ptr)){
  733.     return;            /* there are no word entries to write */
  734.   }
  735.   /* printf("Flushing word %s\n", wrd_entry->word); */
  736.   /* if this is the entry for this word, the put in the dictionary
  737.      entry in the index file */
  738.   write_dictionary_index_block(wrd_entry->number_of_occurances,
  739.                    wrd_entry->word,
  740.                    db->index_stream);
  741.  
  742.   db->number_of_words++;
  743.  
  744.   /* allocate and write the new block */
  745.   allocate_index_block(wrd_entry->current_memory_ptr -
  746.                wrd_entry->memory_ptr +
  747.                INDEX_BLOCK_HEADER_SIZE,
  748.                db->index_stream);
  749.   /* cprintf(PRINT_AS_INDEXING, "New block number: %ld\n", new_block); */
  750.   if((wrd_entry->current_memory_ptr - wrd_entry->memory_ptr) !=
  751.      fwrite(wrd_entry->memory_ptr, 1L, (wrd_entry->current_memory_ptr -
  752.                     wrd_entry->memory_ptr),
  753.         db->index_stream))
  754.     panic("Write failed");
  755.   /* free the memory for the block written out */
  756.   free_word_occurance_block(wrd_entry->memory_ptr);
  757.   wrd_entry->memory_ptr =  NULL;
  758.   wrd_entry->current_memory_ptr = NULL;
  759.   wrd_entry->memory_size = 0;
  760.   wrd_entry->current_doc_id = 0;
  761. }
  762.   
  763.  
  764. /* This flushes all of the memory version of the word hashtable to disk.
  765.  * this is called when the hashtable is filling up or we have 
  766.  * accumulated enough words.  If completely is true, then it will merge 
  767.  * all the intermediate files.
  768.  */
  769. void flush_memory_hashtable_to_disk(db,completely)
  770. database* db;
  771. boolean completely;
  772. {
  773.   /* map over the memory word hashtable and write the entries to disk */
  774.   long i;
  775.   char filename[1000];
  776.  
  777.   db->index_stream = 
  778.     s_fopen(index_filename_with_version(db->index_file_number++, filename, db),
  779.         "wb");
  780.   if(NULL == db->index_stream)
  781.     panic("Could not open file %s to insert index", 
  782.       index_filename_with_version(db->index_file_number, filename, db));
  783.  
  784.   waislog(WLOG_MEDIUM, WLOG_INDEX,
  785.       "Flushing %ld different words, %ld total words to disk...", 
  786.       db->the_word_memory_hashtable->number_of_entries,
  787.       db->the_word_memory_hashtable->number_of_words_indexed);
  788.  
  789.   db->number_of_words = 0;
  790.  
  791.   write_bytes(0l, INDEX_HEADER_SIZE, db->index_stream);
  792.   collapse_word_memory_hashtable(db->the_word_memory_hashtable); /* compact the entries to the bottom */
  793.   sort_word_memory_hashtable(db->the_word_memory_hashtable); /* sort the entries */
  794.   for(i = 0; i < db->the_word_memory_hashtable->number_of_entries; i++){
  795.     if(NULL != db->the_word_memory_hashtable->contents[i]){
  796.       /* then we have an entry to write */
  797.       word_entry* the_word_entry = db->the_word_memory_hashtable->contents[i];
  798.       flush_word_entry_to_file(the_word_entry, db);
  799.     }
  800.   }
  801.  
  802.   /* write out the number of entries into the index_file header */
  803.   s_fseek(db->index_stream, 0L, SEEK_SET);
  804.   write_bytes(db->number_of_words, INDEX_HEADER_SIZE, db->index_stream);
  805.   s_fclose(db->index_stream);
  806.  
  807.   /* since everything is written out, we can flush these. */
  808.   flush_word_occurance_buffers(); 
  809.   clear_word_memory_hashtable(db->the_word_memory_hashtable);
  810.   /* add the stopwords to the index for the next session. */
  811.   add_stop_words(db->the_word_memory_hashtable);
  812.  
  813.   waislog(WLOG_MEDIUM, WLOG_INDEX,
  814.       "Done flushing");
  815.   /* scan_index_blocks(filename); */
  816.  
  817.   if(completely){
  818.     waislog(WLOG_MEDIUM, WLOG_INDEX,
  819.         "Merging %ld files",
  820.         db->index_file_number);
  821.     merge_index_files(db);
  822.     waislog(WLOG_MEDIUM, WLOG_INDEX,
  823.         "Done merging.");
  824.   }
  825. }
  826.  
  827. long finished_add_word(db)
  828. database *db;
  829. {
  830.   flush_memory_hashtable_to_disk(db,true);
  831.   return(0); /* successful */
  832. }
  833.  
  834. long init_add_word(db, hashtable_size, flush_after_n_words)
  835.      database *db;
  836.      long hashtable_size;
  837.      long flush_after_n_words;
  838. {
  839.   db->the_word_memory_hashtable =
  840.     init_word_memory_hashtable(hashtable_size, 
  841.                    flush_after_n_words, 
  842.                    db->the_word_memory_hashtable);
  843.   return(0);
  844. }
  845.